package leetcode_1601_1700;

public class LeeCode_1643 {
    public static void main(String[] args) {
        System.out.println(kthSmallestPath(new int[]{2,3}, 3));
    }
    private static String kthSmallestPath(int[] destination, int k) {
        int cv = destination[0], ch = destination[1];
        StringBuilder sb = new StringBuilder();
        if (cv == 0){
            for (int i = 0; i < ch; i++) {
                sb.append('H');
            }
            return sb.toString();
        }
        if (ch == 0){
            for (int i = 0; i < cv; i++) {
                sb.append('V');
            }
            return sb.toString();
        }
        int n = cv + ch;
        long smaller = get(n - 1, Math.min(n - 1 - (ch - 1), ch - 1));
        if (k <= smaller){
            sb.append('H');
            sb.append(kthSmallestPath(new int[]{cv, ch - 1}, k));
        }else {
            sb.append('V');
            sb.append(kthSmallestPath(new int[]{cv - 1, ch}, (int) (k - smaller)));
        }
        return sb.toString();
    }
    private static long get(int n, int m){
        long up = 1, down = 1;
        for (int i = n - m + 1; i <= n; i++) {
            up *= i;
        }
        for (int i = 1; i <= m; i++) {
            down *= i;
        }
        return up / down;
    }
}